package leetcode_141_160;

import utils.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class sortList_148 {
    /**
     * 按 升序 排列并返回 排序后的链表
     * 进阶：在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
     */
    public ListNode sortList(ListNode head) {
        /**
         * 不考虑进阶要求
         * 思路很简单，存储所有节点后对其排序后逐个连接
         * 12ms
         */
        if(head==null || head.next==null)
            return head;
        List<ListNode>list=new ArrayList<>();
        ListNode root=head;
        while(root!=null){
            list.add(root);
            root=root.next;
        }
        Collections.sort(list,( listNode1,listNode2 )->listNode1.val-listNode2.val);

        ListNode sortedList=list.get(0);
        ListNode root2=sortedList;
        for (int i=1;i<list.size();i++){
            root2.next=list.get(i);
            root2=root2.next;
        }
        root2.next=null;
        return sortedList;
    }


    /**
     * 高解思路，利用快慢指针，在递归的每一层将链表分隔为两半
     * 这样每层递归都是处理两个有序链表
     * 自底向上将所有有序链表合并
     * 11ms
     * @param head
     * @return
     */
    public ListNode sortList2(ListNode head) {
        // 1、递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 2、找到链表中间节点并断开链表 & 递归下探
        ListNode midNode = middleNode(head);
        //右半部分
        ListNode rightHead = midNode.next;
        midNode.next = null;

        //进入下层递归，分别处理两部分链表
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        // 3、当前层业务操作（合并有序链表）
        return mergeTwoLists(left, right);
    }

    //  找到链表中间节点（876. 链表的中间结点）
    private ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // 合并两个有序链表（21. 合并两个有序链表）
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode sentry = new ListNode(-1);
        ListNode curr = sentry;

        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }

            curr = curr.next;
        }

        curr.next = l1 != null ? l1 : l2;
        return sentry.next;
    }
}



